package chapter03_binaryTree;

/**
 * 描述：
 *      找到二叉树某个结点的后继结点
 *      后继结点：在中序遍历生成的序列中，node的下一个结点叫做node的后继结点
 *      方法一：二叉树结点的结构有正确指向父节点的指针，那么一直想上找就可以找到头结点，
 *      然后进行整个二叉树的中序遍历，既可以得到指定的结点的后继结点， 时间复杂度为O(n),空间复杂度为O(n)
 *      方法二：node的后继结点一定在node的right结点或者父节点及祖先结点中。分情况讨论：
 *          1)如果node.right != null,那么node的后继结点是右子树的最左结点
 *          2)如果node.right == null,那么向上找,将当前结点记为s,s的结点记为p,直到p.left == s,此时p为node后继结点
 *          3)如果情况2中一直到p == null也找到符合条件的p结点,那么node.right为空，node是整个二叉树的最右结点
 *          时间复杂度最大也就是二叉树的高度O(logN)
 * @author hl
 * @date 2021/5/30 11:57
 */
public class GetNextNode {

    public Node getNextNode(Node node){
        if (node == null) {
            return null;
        }
        if (node.right != null) {
            return getLeftMost(node.right);
        }else{
            Node p = node.parent;
            while(p != null && p.left != node){
                node = p;
                p = node.parent;
            }
            return p;
        }
    }

    private Node getLeftMost(Node node) {
        if (node == null) {
            return null;
        }
        while(node.left != null){
            node = node.left;
        }
        return node;
    }

    static class Node{
        int val;
        Node left;
        Node right;
        Node parent;

        public Node(int val) {
            this.val = val;
        }
    }
}
